package leetcode.hot100;

import leetcode.tester.Tester;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Stack;
import java.util.stream.Stream;

/**
 * 42. 接雨水
 * https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author Liu Yicong
 * @date 2025/10/14
 */
public class Hot7DbpTrap {
	public static void main(String[] args) {
		int[] inp = null;
		try (Stream<String> lines = Files.lines(Paths.get("src/data/Hot7DbpTrap.txt"))) {
			inp = lines
					.flatMap(line -> Arrays.stream(line.replaceAll("[\\[\\]]", "").split(",")))
					.map(String::trim)
					.mapToInt(Integer::parseInt).toArray();
		} catch (IOException e) {
			e.printStackTrace();
		}

		Object[][] inputs = {
				new Object[]{new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}},
				new Object[]{new int[]{4, 2, 0, 3, 2, 5}},
				new Object[]{new int[]{3, 0, 2, 1, 2}},
				new Object[]{new int[]{3, 1, 2, 1, 2, 3}},
				new Object[]{new int[]{5, 4, 1, 2}},
				new Object[]{inp}
		};

		Object[] outputs = {
				6, 9, 3, 6, 1, 949905000
		};

		Tester.test(Tester.wrap(new Hot7DbpTrap()::trap), inputs, outputs);
		Tester.test(Tester.wrap(new Hot7DbpTrap()::trapDbp), inputs, outputs);
		Tester.test(Tester.wrap(new Hot7DbpTrap()::trapDbpOpt), inputs, outputs);
		Tester.test(Tester.wrap(new Hot7DbpTrap()::trapStack), inputs, outputs);
	}

	/**
	 * 使用扫描两遍的方法，并使用两个dp数组记录扫描过的最高位置。
	 */
	public int trap(int[] height) {
		int n = height.length;
		int maxH = 0;
		int[] dpLeft = new int[n];
		for (int i = 0; i < n; i++) {
			maxH = Math.max(height[i], maxH);
			dpLeft[i] = maxH;
		}
		int[] dpRight = new int[n];
		maxH = 0;
		for (int i = n - 1; i >= 0; i--) {
			maxH = Math.max(height[i], maxH);
			dpRight[i] = maxH;
		}
		int res = 0;
		for (int i = 0; i < n; i++) {
			res += Math.min(dpLeft[i], dpRight[i]) - height[i];
		}
		return res;
	}

	/**
	 * 使用双指针的方法, 双指针的方法是对动态规划方法的一种优化.
	 * 在动态规划的做法中, 需要维护长度为n的两个数组, 那么如何减少空间复杂度?
	 * 到下标i处的能接的雨水量由dpr[i]和dpl[i]中的较小值决定, 这两个数组就可以使用两个指针来代替
	 */
	public int trapDbp(int[] height) {
		int n = height.length;
		int res = 0;
		int l = 0, r = n - 1, lMax = 0, rMax = 0;
		while (l < r) {
			lMax = Math.max(lMax, height[l]);
			rMax = Math.max(rMax, height[r]);
			if (rMax > lMax) {
				res += lMax - height[l];
				l++;
			} else {
				res += rMax - height[r];
				r--;
			}
		}
		return res;
	}

	/**
	 * 优化了lMax和rMax的更新的过程
	 */
	public int trapDbpOpt(int[] height) {
		int n = height.length;
		int res = 0;
		int l = 0, r = n - 1, lMax = height[l], rMax = height[r];
		while (l < r) {
			if (rMax > lMax) {
				res += lMax - height[l];
				l++;
				if (l <= r) lMax = Math.max(lMax, height[l]);
			} else {
				res += rMax - height[r];
				r--;
				if (l <= r) rMax = Math.max(rMax, height[r]);
			}
		}
		return res;
	}


	/**
	 * 使用单调栈的方法
	 * 单调栈可以解决的问题比较单一: 在数组中寻找下一个更大(小)的元素.
	 * 首先让遍历的当前元素入栈, 如果当前元素大(小)于栈顶元素, 那么就让当前元素出栈, 否则则保持在栈内的状态, 直到有元素大于该元素再出栈
	 * 下面就是一个通过单调栈来查找每个元素右侧更大元素的过程, 注意栈内的元素应存储为索引而不是数值, 这里仅为方便理解.
	 * arr     4   2   0   3   2   5       arr     4   2   0   3   2   5       arr     4   2   0   3   2   5
	 * -       i                                       i                                       i
	 * stack   4                           stack   4   2                       stack   4   2   0
	 * res     -1                          res     -1  -1                      res     -1  -1  -1
	 * <p>
	 * arr     4   2   0   3   2   5       arr     4   2   0   3   2   5       arr     4   2   0   3   2   5
	 * -                   i                                       i                                       i
	 * stack   4                           stack   4                           stack
	 * res     -1  3   3                   res    -1   3   3   2               res     5   3   3   2   5
	 * <p>
	 * 对于本题来说, 需要查找每个位置中左右两侧都大于第i个元素的位置(即左右侧的柱子).
	 * 对于单调栈来说, 显然右侧的柱子就是下一个更大的元素, 记当前元素就是栈顶top, 那么左侧的柱子即为栈内top的下一个元素即为left.
	 */
	public int trapStack(int[] height) {
		int n = height.length;
		int res = 0;
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < n; i++) {
			while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
				Integer top = stack.pop();
				if (stack.isEmpty()) {
					break;
				}
				int left = stack.peek();
				int w = i - left - 1;
				int h = Math.min(height[left], height[i]) - height[top];
				res += w * h;
			}
			stack.add(i);
		}
		return res;
	}
}
